#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

class BinaryTree:
    NINF = -9999999     # 负无穷大
    INF =  9999999

    def __init__(self, root):
        self.root = root

    def is_binary_tree(self):
        # return self.is_binary_tree_method1()
        return self.is_binary_tree_method2()

    def is_binary_tree_method1(self):
        # 第一种方法: 自己想出来的
        if not self.root:
            return True

        valid, min, max = self._process_node(self.root)
        # if not valid:
        #     print(min, max)
        return valid

    def _process_node(self, node):
        min_l = max_l = node.value
        min_r = max_r = node.value
        valid_l = valid_r = True

        if node.left:
            valid_l, min_l, max_l = self._process_node(node.left)
        if node.right:
            valid_r, min_r, max_r = self._process_node(node.right)

        if not (valid_l and valid_r):
            print('left or right failed %s' % node.value)
            return False, None, None

        if not max_l <= node.value <= min_r:
            print('valud failed %s' % node.value)
            return False, None, None

        return True, min_l, max_r

    # ===================  =====================
    def is_binary_tree_method2(self):
        left, right = self.NINF, self.INF
        return self._is_valid_node(self.root, left, right)

    def _is_valid_node(self, node, left, right):
        if not node:
            return True

        mid = node.value
        if not left <= mid <= right:
            print('bad value %s' % mid)
            return False

        return self._is_valid_node(node.left, left, mid) and \
                self._is_valid_node(node.right, mid, right)

def test():
    l = Node(3, Node(1), Node(4))
    r = Node(8, Node(7), Node(12))
    root = Node(5, l, r)
    # root = Node(5)

    b = BinaryTree(root)
    v = b.is_binary_tree()
    print(v)

    # l = Node(3, Node(1), Node(4))
    # r = Node(8, Node(7), Node(12))
    # root = Node(5, l, r)


def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
